
#include "Stack.h"


//交换函数
void Swap(float* p1, float* p2)
{
	float tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//三数取中
int GetMinIndex(float* arr, int left, int right)
{
	int mid = (left + right) >> 1;
	if (arr[left] < arr[mid])
	{
		if (arr[mid] < arr[right])
		{
			return mid;
		}
		if (arr[left] < arr[right] && arr[right] < arr[mid])
		{
			return right;
		}
		return left;
	}
	else//arr[left] >= arr[mid]
	{
		if (arr[left] < arr[right])
		{
			return left;
		}
		if (arr[mid] < arr[right] && arr[right] < arr[left])
		{
			return right;
		}
		return mid;
	}
}

//快排非递归
void QuickSort(float* arr, int n)
{
	ST st;
	StackInit(&st);

	//把左右区间压栈，先压右边
	StackPush(&st, n - 1);
	//后压左边
	StackPush(&st, 0);

	//只要栈不为空，就继续分割排序
	while (!StackEmpty(&st))
	{
		//从栈里面取出左右区间
		int left = StackTop(&st);
		StackPop(&st);
		int right = StackTop(&st);
		StackPop(&st);
		int index = GetMinIndex(arr, left, right);
		//因为我们下面的逻辑都是把第一个数作为key，
		//为了避免改动代码，这里我们直接交换就可以
		Swap(&arr[left], &arr[index]);
		//开始单趟排序
		int begin = left;
		int end = right;
		int pivot = begin;
		float key = arr[begin];

		while (begin < end)
		{
			//end开始找小
			while (begin < end && arr[end] >= key)
			{
				end--;
			}
			arr[pivot] = arr[end];
			pivot = end;
			//begin开始找大
			while (begin < end && arr[begin] <= key)
			{
				begin++;
			}
			arr[pivot] = arr[begin];
			pivot = begin;
		}
		pivot = begin;
		arr[pivot] = key;

		//区间分为[left,pivot-1]pivot[pivot+1,right]
		//利用循环继续分割区间
		//先入右子区间
		if (pivot + 1 < right)
		{
			//说明右子区间不止一个数
			//先入右边边界
			StackPush(&st, right);
			//再入左边边界
			StackPush(&st, pivot+1);
		}

		//再入左子区间
		if (left < pivot-1)
		{
			//说明左子区间不止一个数
			//先入右边边界
			StackPush(&st, pivot-1);
			//再入左边边界
			StackPush(&st, left);
		}	
	}
	StackDestory(&st);
}
